package com.copa.l94;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author copa
 * @createDate 2022-05-19 09:11
 * @function 迭代法
 */
public class Test2 {

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        // 注意 中序遍历的顺序是：左 根 右
        // 定义栈，存放临时二叉树
        Stack<TreeNode> stack = new Stack<>();
        // 定义临时指针，方便指向
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                // 如果当前指针指向的二叉树不为空，则应该入栈，并且向左子树移动
                stack.push(cur);
                cur = cur.left;
            } else {
                // 如果此时指针指向的二叉树为空，那么此时就把临时指针指向出栈的二叉树，并且加入到结果集并向右子树移动
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode();
        treeNode.val = 1;
        treeNode.right = new TreeNode(2);
        treeNode.right.left = new TreeNode(3);
        List<Integer> result = new Test2().inorderTraversal(treeNode);
        System.out.println(Arrays.toString(result.toArray()));
    }
}
